namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0141. 环形链表")]
    public class No0141_HasCycle : AbsBaseTestItem
    {
        /*
        给定一个链表，判断链表中是否有环。
        如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
        如果链表中存在环，则返回 true 。 否则，返回 false 。

        进阶：
        你能用 O(1)（即，常量）内存解决此问题吗？

        提示：
            链表中节点的数目范围是 [0, 104]
            -105 <= Node.val <= 105
            pos 为 -1 或者链表中的一个 有效索引 。
        */

        public class ListNode
        {
            public int val;
            public ListNode next;
            public ListNode(int x)
            {
                val = x;
                next = null;
            }
        }

        public override void OnTest()
        {
            // 示例 1:
            ListNode node = new ListNode(3)
            {
                next = new ListNode(2)
                {
                    next = new ListNode(0)
                    {
                        next = new ListNode(-4),
                    },
                },
            };
            node.next.next.next.next = node.next;
            Assert.TestExe(HasCycle, node, true);

            // 示例 2:
            node = new ListNode(1)
            {
                next = new ListNode(2),
            };
            node.next.next = node;
            Assert.TestExe(HasCycle, node, true);

            // 示例 3:
            node = new ListNode(1);
            Assert.TestExe(HasCycle, node, false);
        }

        public bool HasCycle(ListNode head)
        {
            if (head == null || head.next == null)
                return false;
            ListNode slow = head;
            ListNode fast = head.next;
            while (slow != fast)
            {
                if (fast == null || fast.next == null)
                    return false;
                slow = slow.next;
                fast = fast.next.next;
            }
            return true;
        }
    }
}
